The present invention relates to improved apparatus and methods for detecting and correcting data errors in a data processing system. More particularly, the present invention relates to improved apparatus and methods for detecting and correcting data errors in data having relatively high raw error rates and also containing multiple relatively long burst errors occurring randomly in the data streams such as may occur, for example, in an optical data storage system.
Conventional storage devices, such as magnetic disks, typically have a relatively low raw bit error rate of the order of 10.sup.-9. As a result, relatively simple single-short-burst error detecting and correcting methods and apparatus have been found sufficient for use with such devices for providing an effective bit error rate of typically 10.sup.-12 or lower, as conventionally required in order to provide adequate system-level performance. However, where data having a much higher raw bit error rate, such as 10.sup.-5 must be detected and corrected, these known error detecting methods and apparatus are unable to provide an effective bit error rate which is adequate for conventional system-level performance. Furthermore, where data read from an optical data storage system is involved, the additional difficulty is presented of having to deal with the presence of relatively long multiple burst-errors occurring randomly in the data stream.
Reed-Solomon codes are known to be capable of detecting and correcting multiple burst errors. Methods and apparatus for using this type of code for correcting such errors has been disclosed in the art, such as, for example, in U.S. Pat. No. 4,009,160 issued July 4, 1978 and U.S. Pat. No. 4,142,174 issued Feb. 27, 1979, and also in the book by W. W. Peterson, et al., "Error Correcting Codes", Cambridge, Mass., The MIT Press, 1972, and in the article by E. R. Berlekamp, "The Technology of Error-Correcting Codes", Proc. of the IEEE, Vol. 68, No. 5, pp. 564-593, May 1980. In addition, my Thesis "High Speed Decoding of Reed-Solomon Codes", M. S. Thesis, University of Hawaii, December 1981, presents additional implementations along with basic theoretical considerations pertinent to the use of Reed-Solomon codes for detecting and correcting data errors. The contents of these publications are hereby incorporated herein.
Although a number of theoretical approaches are known for employing Reed-Solomon codes for error detection and correction (as exemplified by the references mentioned above), implementations of such known approaches require complex and expensive hardware, particularly where it is required that error detection and correction be performed sufficiently fast so as to be on-line with the system in which it is employed.